package sortedAlgorithmCollections;

/**
 * @author le
 */
public class QuickSort {

    public static void main(String[] args) {

        // 待排序的数组
        int[] nums = {1, 56, 8, 9, 65, 88,10};

        sort(nums,0,nums.length-1);

        for (int num : nums) {
            System.out.println(num);
        }

    }

    /**
     * 快速排序
     * @param arr 待排序的数组
     * @param left 数组的左边界
     * @param right 数组的有边界
     */
    public static void sort(int[] arr, int left, int right){

        if (left < right) {
            // 用来比较的值 是 第一个元素的值
            int key = arr[left];

            // 左右边界
            int i = left;
            int j = right;

            while (i < j) {
                while (i < j && arr[j] > key) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
                while (i < j && arr[i] < key) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = key;
            sort(arr, left, i - 1);
            sort(arr, i + 1, right);
        }
    }
}
